A packet switch is a node in a digital data network that receives data packets from multiple network communication links, temporarily stores and then forwards the data packets onto other links, as directed by the configuration of the packet switch. Upon ingress, packets are classified to belong to a particular data flow that allows packets to egress towards one or more communication links. Storage of packet flows is necessary to ensure proper handling when multiple packets ingress simultaneously, and is typically handled by a plurality of queues. Although packet switches may perform various tasks, a common task is to “shape” each data flow to have a selected egress rate of data packets.
As illustrated in FIG. 1, a conventional packet switch 10 includes a queuing system 11 for storing packets, the egress behavior of which is governed by a scheduler 12 and a shaper 14. Queueing system 11 conveys data packets received at an input port 16 to an output port 18 in the form of a number of logical flows (i.e., streams or flows of data packets addressed to a corresponding number of destinations). Scheduler 12 determines which flow will be the next to egress from queuing system 11. Shaper 14 includes a set of accumulators 20A, 20B, 20C, etc. (which may be referred to collectively as accumulators 20). A controller 22, which may comprise a state machine, controls the operation of shaper 14.
Shaper 14 controls the flow of data packets through packet switch 10 by coordinating with queuing system 11 and scheduler 12. Shaper 14 performs a data flow shaping function in accordance with what is commonly referred to as a form of the “leaky bucket algorithm.” The queuing system 11 includes a memory in which queues 24A, 24B, 24C, etc. (which may be referred to collectively as queues 24) are implemented. Each of queues 24 corresponds to one of the data flows. As data packets are received at input port 16, an ingress classifier 25 allocates them to the queues 24 corresponding to the data flows. When one or more queues 24 are not empty, the scheduler 12 must determine which flow within the queuing system 11 shall be the next one selected to egress traffic. Various algorithms for choosing an egress flow are well known and commonly include metrics such as prioritization, fairness, and allocate on the basis of a target egress rate on a per-flow basis. For example, the algorithm may allocate packets with the goal that one data flow has an average egress rate of five megabits per second (Mb/s) while another data flow has an average egress rate of 10 Mb/s.
Each of accumulators 20 in shaper 14 corresponds to one flow (which may in turn correspond to one or more queues 24 or one or more physical ports) and maintains a count or credit balance that increases at the maximum rate at which scheduler 12 requests the flow to egress packet data from the queuing system 11. In some conventional shaper implementations, the accumulators may comprise numerically controlled oscillators or similar counters that increment at a constant rate.
Controller 22 monitors the count or number of credits in each of accumulators 20 by, for example, sequentially polling them. The number of credits in each of accumulators 20 represents the number of bits of data available to send from the corresponding flow while still maintaining the desired egress rate limit. Each time controller 22 polls one of accumulators 20 it determines whether the corresponding flow (i.e., the metaphorical “bucket”) has filled with a number of credits to support egress of one or more data packets by determining if the number of credits contained in the corresponding one of accumulators 20 is between a predetermined minimum threshold for sending and predetermined maximum credit level, beyond which additional credit cannot be built up. If the number of credits is within that range, then controller 22 transmits a message to scheduler 12 indicating that scheduler 12 is permitted to transmit one or more data packets on the corresponding data flow. For purposes of clarity, a logical communication path 26 is shown that represents the polling query. Similarly, a logical communication path 28 is shown that represents the results of (or response to) the polling query. Logical communication path 26 can also represent communication of the above-referenced permission. Logical communication paths 26 and 28 are shown in broken line to indicate that they are not direct physical connections; the actual or physical transmission of information representing the polling query and permission message may occur on a connection 30, while the actual or physical transmission of the polling response may occur on a connection 32.
In response to receiving the above-referenced permission message from shaper 14, scheduler 12 may cause queuing system 11 to transmit one or more data packets and then return confirmation information to shaper 14. The confirmation information commonly includes a flow identifier identifying the flow on which the data packet or packets were sent and the number of bits sent. In response to this confirmation information, shaper 14 decrements (by the number of bits sent) the one of accumulators 20 that corresponds to the credit of the flow on which the data packets were sent.
A disadvantage of the above-described conventional shaper 14 is that it is not highly scalable. That is, although the number of data flows out of packet switch 10 can be increased by increasing the number of queues 24 and correspondingly increasing the number of accumulators 20, the duration of sequentially polling accumulators 20 grows proportionally longer. Any given one of accumulators 20 may be polled so infrequently that many queues 24 containing a sufficient number of bits to be eligible to send packets may be excessively delayed from sending packets. Excessive delay in queues 24 sending packets adversely impacts the target egress rates of the flows.